home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tech Arsenal 1
/
Tech Arsenal (Arsenal Computer).ISO
/
tek-02
/
pascala.zip
/
TREEMOD.PAS
< prev
Wrap
Pascal/Delphi Source File
|
1980-01-01
|
4KB
|
125 lines
(*************************************************************)
(* Several procedures for binary tree processing are *)
(* contained in the module below. *)
(* This is NOT a complete module ready to link up with a *)
(* driver program. PRB 10/90 *)
(*************************************************************)
PROGRAM TreeMod(Input,Output);
TYPE DataType = Real;
NodePointer = ^NodeRec;
NodeRec= RECORD
Data: DataType;
Level: 0..Maxint;
LeftLink,
RightLink: NodePointer;
END;
VAR Root: NodePointer;
Seed: Integer;
DataIn: DataType;
(***************************************************)
(* Generates a random number ( 0 <= R < 1 ) *)
(* Seed must be initialized ONCE before using *)
(***************************************************)
FUNCTION Random(VAR Seed: Integer): Real;
CONST Modulus = 65536;
Multiplier = 25173;
Increment = 13849;
BEGIN
Seed:=((Multiplier*Seed) + Increment) MOD Modulus;
Random:= Seed/Modulus;
END;
(***************************************************)
(* Disposes of the nodes of an existing, unneeded *)
(* Tree. Recursively called in postorder. *)
(***************************************************)
PROCEDURE DisposeTree(VAR CurrentNode:NodePointer);
BEGIN
WITH CurrentNode^ DO
BEGIN
IF LeftLink<> nil THEN
DisposeTree(LeftLink);
IF RightLInk<> nil THEN
DisposeTree(RightLink);
Dispose(CurrentNode);
END;
END;
(***************************************************)
(* Recursively searches for node to insert DataIn *)
(* Inserts data DataIn into a tree in order *)
(***************************************************)
PROCEDURE AddaNode(VAR Current: NodePointer;
DataIn: DataType;
CurrentLevel: Integer);
BEGIN
IF Current = nil THEN (* Place is found *)
BEGIN
New(Current);
Current^.Data:= DataIn;
Current^.Level:= CurrentLevel;
Current^.LeftLink:= nil;
Current^.RightLink:= nil;
END
ELSE (* Search farther *)
IF (DataIn < Current^.Data) THEN
AddaNode(Current^.LeftLink, DataIn, CurrentLevel+1)
ELSE
AddaNode(Current^.RightLink, DataIn,CurrentLevel+1); (* Duplicate keys *)
END; (* are inserted in *)
(* original order *)
(**************************************)
(* *)
(**************************************)
PROCEDURE FormTree(VAR Root:NodePointer);
CONST NumberofNodes = 15;
VAR I: Integer;
DataIn: DataType;
(*************************************)
(* Currently randomly generated *)
(*************************************)
PROCEDURE GetData(VAR DataIn: DataType);
BEGIN
DataIn:=100*Random(Seed)+1;
END;
BEGIN (* FormTree *)
Root:= nil;
FOR I:= 1 TO NumberofNodes DO
BEGIN
GetData(DataIn);
AddaNode(Root, DataIn, 0);
END;
END;
(**********************************************)
(* ShowTree Recursively displays a tree *)
(* in L-R order. *)
(**********************************************)
PROCEDURE ShowTree(CurrentNode: NodePointer);
BEGIN
WITH CurrentNode^ DO
BEGIN (* Reversed for rotated display *)
IF RightLink<> nil THEN
ShowTree(RightLink);
Writeln(' ',Trunc(Data):3*(1+Level));
IF LeftLink<>nil THEN
ShowTree(LeftLink);
END;
END;
BEGIN (************* MAIN *************)
(* Initialize *)
(* Describe *)
Write('Enter seed for the Random function: ');
Readln(Seed); Writeln;
FormTree(Root);
Writeln; Writeln; Writeln;
ShowTree(Root);
DisposeTree(Root);
END.